算法学习Day 1| 二分法详解

二分法详解

1 二分法

 暴力法遍历有序数列：O(n)，二分法（一种查找或确定函数根的方法）减少到O(logn)，例如猜数游戏(二分猜测次数log_{2}n)，若n=1e7，则只需要猜log_{2}10^7 =23.25次，向上取整24次，（一个亿27次）

理论背景：非线性方程求根，不用管

1.1 猜数游戏

一个[1，100]内的数字，只需猜7次:

50?是。[1，100]二分，中位数50，下一步猜[51,100]
75?否。[51,100]二分，中位数75，下一步猜[51,75]
63?否。[51,75]二分,
56?否。[51,63]二分，
53?是。
54?否。
=54?是。这个数是54

1.1.1 猜数游戏代码
首先确定左端点和右端点，如果左端点<右端点就一直循环，不断更新中间值mid =(right+left)//2。如果目标点在左半区，右端点往中间靠right= mid，如果目标点在右半区， 左端点往中间靠left = mid+1，直到循环结束，左端点或者右端点就是目标值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def bin_search(a, n, x):             # 在数组a中找数字x，返回位置
    left = 0                         # 二分法的左端点
    right = n                        # 二分法的右端点
    while left < right:              # 右端点大于左端点则继续二分
        mid = (right + left) // 2  # 折半前的中间点。//：整除
        # mid = left + (right + left)//2  # C++有溢出问题，Python没有
        if a[mid] >= x:
            right = mid                    # 小于中间点则中间点作为右端点
        else: # a[mid] < x,只是大于，所以要left = mid + 1
            left = mid + 1                 # 大于中间点则中间点作为左端点
        print('[', left, right, ']') # 打印猜数的过程
    return left

n = 100
a = [0] + [i for i in range(1, 101)] **##为什么要加[0]？**# #初始化1~100
#
test = 54                           # #猜54这个数
pos = bin_search(a, n, test)        # 二分搜索
print("test=", a[pos])

D:\python.exe F:\Pycharm\算法训练营\二分法.py 
[ 51 100 ]
[ 51 75 ]
[ 51 63 ]
[ 51 57 ]
[ 51 54 ]
[ 53 54 ]
[ 54 54 ]
test= 54

1.2 二分法使用条件

   上下界[a,b]确定，函数在界内单调

1.3 二分法复杂度

1.3.3 二分法的核心原理

每次将区间一分为二，缩小区间范围。例如：

  • 初始区间长度是 b - a（如从a=0到b=100000，长度是100000）。
  • n次二分后，区间长度缩小为 (b - a) / 2ⁿ（指数级缩小）。

1.3.2. 如何计算二分次数n？

根据精度要求（ξ），需满足：

(b - a) / 2ⁿ < ξ

解这个不等式可得：

n > log₂[(b - a) / ξ]

即：二分次数n需满足以2为底的对数关系。

补充：二分精度要求为1是否等同于整数二分？

精度要求为ξ=1时，并不严格等同于“整数二分”，但两者在特定场景下可能结果一致。以下是详细分析：

1. 精度ξ=1的含义

根据图中的公式 (b-a)/2ⁿ < ξ，当ξ=1时，条件变为 (b-a)/2ⁿ < 1。

  • 最终区间长度：经过n次二分后，区间长度必须小于1。
  • 结果取值：此时区间的中点或端点可以是实数，但若问题中所有值均为整数，则结果自然为整数。
  • 示例：
    在区间 [0, 100] 中查找整数解，若ξ=1，需满足 100/2ⁿ < 1 → n > log₂(100) ≈ 6.64 → n=7次。
    最终区间长度为 100/(2^7) ≈ 0.781 < 1，取中点时结果为整数（如49.5取整为49或50）。

2. 整数二分的定义

整数二分是一种特殊场景，通常指：

  • 操作对象：仅处理整数区间（如数组索引、离散值）。
  • 终止条件：当区间无法再分割（即左右指针相邻或重合）时停止，无需依赖ξ=1。
  • 结果性质：最终结果必为整数，且计算过程中所有中间值（如mid）均为整数。

3. 关键区别与联系

场景 精度ξ=1的实数二分 整数二分
适用范围 实数或整数区间 仅限整数区间（如数组索引）
终止条件 区间长度<1（可能含小数） 左右指针重合或相邻（区间长度=0或1）
结果取值 可四舍五入到整数 直接得到整数
计算过程 mid可为小数（如 (0+1)/2=0.5） mid强制为整数（如 (0+1)//2=0）
复杂度逻辑 符合图中的公式 n > log₂[(b-a)/ξ] 通常无需计算ξ，直接按整数分割

4. 实际应用中的表现

(1) 若问题本身是整数二分（如数组查找）

  • 无需设置ξ=1：通过强制mid为整数（如 mid = (l + r) // 2），自然保证结果在整数范围内。
  • 示例：在有序数组 [1,3,5,7,9] 中查找4的插入位置，结果为索引2（整数），与ξ=1的实数二分结果一致，但实现方式不同。

(2) 若问题为实数二分但要求结果为整数

  • 设置ξ=1：通过 n > log₂(b-a) 次二分后，取中点或端点并四舍五入，结果可强制为整数。
  • 示例：求函数 f(x)=x²-2 在 [1,2] 内的根（精确到整数），ξ=1时结果为1（实际根为√2≈1.414，但取整后为1）。

5. 结论

  • 精度ξ=1 ≠ 整数二分：
    • ξ=1是实数二分中精度控制的参数，结果可能为整数，但过程允许非整数中间值。
    • 整数二分是操作对象和计算过程均限制为整数的特殊实现。
  • 关联场景：
    • 若问题要求结果为整数且数据为离散值，两种方法结果可能一致，但实现逻辑不同。
    • 若问题本身是连续函数求根，ξ=1可近似视为“取整到整数”，但需注意误差影响。

总结

根据图中的复杂度逻辑和实际应用，二分精度要求为1时，结果可能是整数，但严格意义上的“整数二分”特指在离散整数域上的操作，两者在实现和适用范围上存在差异。

1.3.3. 时间复杂度：O(log n)

  • 二分法的复杂度是对数级别（红色标注的O(log n)）。
  • 原因：每次操作将问题规模减半，需log₂N次操作才能完成（N是初始规模）。

1.3.4. 举例验证

假设：

  • 区间为[0, 100000]，精度要求为10⁻⁸。
  • 计算：(100000 - 0) / 2ⁿ < 10⁻⁸ → 2ⁿ > 10¹³ → n > log₂(10¹³)
    因log₂(10)≈3.3219，所以 n > 13×3.3219≈43.18 → 向上取整得n=44次。

1.3.5 总结一下：

  1. 二分法通过指数级缩小区间，效率极高。
  2. 二分次数与初始区间长度、精度要求呈对数关系。
  3. 时间复杂度为O(log n)，适用于大规模数据（如例子中仅需44次达到1e-8精度）。

2 整数二分

序列均整数，处理不当容易死循环

2.1 单调递增中查找x或者x的后继（若无x则寻找比x大的下一个数）

求中间值的方法：

mid =(left+right)//2
mid = left+(right-left)//2

a[mid]>=x时:x在mid的左边，新的搜索区间是左半部分，left不变，更新right= mid。
a[mid]<x时:x在mid的右边，新的搜索区间是右半部分，right不变，更新left = mid + 1。
代码执行完毕后，left=right，两者相等，即答案所处的位置。

记忆：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 查找57
def bin_search(a, n, x):  # 在数组a中找数字x，返回位置
    left = 0  # 二分法的左端点
    right = n  # 二分法的右端点  0~n-1:左闭右开[0,n)
    while left < right:  # 右端点大于左端点则继续二分
        mid = (right + left) // 2  # 折半前的中间点。//：整除
        if a[mid] >= x:
            right = mid  # 小于中间点则中间点作为右端点
        else:  # a[mid] < x,只是大于，所以要left = mid + 1
            left = mid + 1  # 大于中间点则中间点作为左端点
    return left
 
 
n = 200
a = **[0]** + [i for i in range(2, 202,2)]  #（len(a)=101）
test = 57
pos = bin_search(a, n, test)  # 二分搜索
print("find =", a[pos]) # find = 58

D:\python.exe F:\Pycharm\算法训练营\二分法.py 
find = 58

注意：若序列中存在多个x，会返回x最后一次出现的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def bin_search1(a,n,x):
    l,r = 0,n
    while l<r:
        mid = (l+r)//2
        if a[mid]>=x:
            r=mid
        else:
            l=mid+1
    return l
 
a = [1,2,2,3,5,5,5,6,7]
print(bin_search1(a,len(a),5))  # 返回5第一次出现的下标:4

**#Py标准库，两个参数：序列、目标值**
# 找4
from bisect import *
a = [1,2,2,3,5,5,5,6,7]
print(bisect_left(a,4))
输出结果：
4
 
# import bisect
# print(bisect.bisect_left(a，4))

2.2 单调递增中寻找x或者x的前驱（若无x则寻找比x小的一个数）

求中间值的方法：

a[mid]<=x时:x在mid的右边，新的搜索区间是右半部分，right不变，更新left = mid 。
a[mid]>x时:x在mid的左边，新的搜索区间是左半部分，left不变，更新right= mid-1。
代码执行完毕后，left=right，两者相等，即答案所处的位置。

背过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def bin_search(a, n, x):  
    left = 0  
    right = n  
    while left < right:  
        mid =  (left+right+1)//2  # 不加上1会陷入死循环
        if a[mid] <= x:
		        left = mid 
        else:          
		        right = mid - 1 
    return left
 
 
n = 200
a = [0] + [i for i in range(2, 202,2)]  
test = 57            # # 猜57或57的后继
pos = bin_search(a, n, test)  # 二分搜索
print("find =", a[pos]) # find = 56

D:\python.exe F:\Pycharm\算法训练营\二分法.py 
find = 56

注意：若序列中存在多个x，会返回x最后一次出现的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def bin_search2(a,n,x):
    l,r = 0,n
    while l<r:
        mid = (l+r+1)//2
        if a[mid]<=x:
            l = mid
        else:
            r = mid-1
    return l
 
a = [1,2,2,3,5,5,5,6,7]
print(bin_search2(a,len(a),5))  # 返回5最后一次出现的下标:6
D:\python.exe F:\Pycharm\算法训练营\二分法.py 
6

和Python 标准库 bisect right()不同，bisect right()返回的下标是应该插入的位置，例如目标值为4的话返回的是下标4，目标值为5的话默认插入在最后一个5后面。关系:bisect right()比我们自己手写的代码bin search2(a,n,x)返回的下标+1。

2.3 对比两种写法

image.png

3 总结：

3.1 二分法应用

1、存在一个有序数列上

2、能够把题目建模在有序数列上查找一个合适的数值

3.2 二分本质

   序列中的元素可以按某个规定的check()方法分为两个部分:一部分的check()为True，另一部分的check()为False。二分完成后，L和R分别指向所属区域临界位置。

4 简易二分模板（推荐！！！不需要考虑前驱和后继）

   假设:L指向check()=True的部分(≤目标值)，R指向check()=False的部分(>目标值)，假设可以根据题目需要来确定。
   二分完成后，L和R分别指向所属区域的**临界位置(终止条件:l+1=r)**
   **注意**:左端点和右端点的初始化要定义在**范围外**，l,r=-1,n+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def check():
    # 具体的check函数
    pass

def bin_search(a, n, x):
    l, r = -1, n + 1
    while l + 1 != r:
        mid = (l + r) // 2
        if check(mid):
            l = mid
        else:
            r = mid
    return (l or r)  # 选取需要的部分进行返回

# 举例：套用这个模板把区间划分成≤5和>5两块，返回左边界:5的最后一个的下标。
# 把边界划分成≤5和＞5两块
def bin_search2(a, n, x):
    l, r = -1, n  # 左闭右开[0,n)：范围0~n-1
    while l + 1 != r:
        mid = (l + r) // 2
        if a[mid] <= x:
            l = mid
        else:
            r = mid
    return l  # 返回左边界

a = [1, 2, 2, 3, 5, 5, 5, 6, 7]
print(bin_search2(a, len(a), 5))  # 6
#若想返回5的第一个的下标，把区间划分成<5和>5，返回右边界r。修改部分代码即可
# 将上面的代码中间修改成这部分代码
        if a[mid]>=x:
            r = mid
        else:
            l = mid
    return r # 返回右边界